1295D - Same GCDs - CodeForces Solution

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

#include <vector>

#define PB push_back

#define MP make_pair

#define PII pair<int,int>

#define FIR first

#define SEC second

#define ll long long

using namespace std;

template <class T>

inline void rd(T &x) {

	x=0; char c=getchar(); int f=1;

	while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }

	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;

}

ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }

int pri[100010],num,d[100010];

void getpri(int n) {

    for(int i=2;i<=n;++i) {

        if(!d[i]) pri[d[i]=++num]=i;

        for(int j=1;j<=d[i]&&i*(ll)pri[j]<=n;++j)

            d[i*pri[j]]=j;

    }

}

vector<ll> fac;

ll cal(ll L,ll R,ll n) {

    for(int j=1;j<=num&&pri[j]*(ll)pri[j]<=n;++j) if(n%pri[j]==0) {

        while(n%pri[j]==0) n/=pri[j];

        fac.PB(pri[j]);

    }

    if(n>1) fac.PB(n);

    int m=fac.size();

    ll ans=0;

    for(int i=0;i<(1<<m);++i) {

        ll d=1; int mu=1;

        for(int j=0;j<m;++j) if(i>>j&1)

            d*=fac[j],mu=-mu;

        ans+=mu*(R/d-L/d);

    }

    fac.clear();

    return ans;

}



int main() {

    getpri(100000);

    int T; rd(T);

    while(T--) {

        ll a,m; rd(a),rd(m);

        ll d=gcd(a,m);

        printf("%lld\n",cal((a-1)/d,(a+m-1)/d,m/d));

    }

    return 0;

}